//
//  main.c
//  02-选择排序
//
//  Created by zhongad on 2017/1/9.
//  Copyright © 2017年 zhongad. All rights reserved.
//

#include <stdio.h>
#include "Swap.h"
#include <time.h>
#include <stdlib.h>

// 选择排序  平均时间复杂度O(n^2) 额外空间复杂度O(1)
void selection_sort(int arr[], int len) {
    int i, j, min, temp;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++)
            if (arr[min] > arr[j])
                min = j;
        temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

// 所用时间:109013微秒
int main(int argc, const char * argv[]) {
    // 计算时间
    int arr[10000];
    for (int i = 0; i < 10000; i++) {
        arr[i] = random() % 10000;
    }
    int len = (int) sizeof(arr) / sizeof(*arr);
    clock_t start, end;
    start = clock();
    selection_sort(arr, len);
    end = clock();
    printf("所用时间:%f\n", (double)(end - start) / CLOCKS_PER_SEC);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}
